#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

#define flr(x,l,r) for (int x = l; x <= r; ++ x)
#define frl(x,r,l) for (int x = r; x >= l; -- x)
#define LL long long 
#define mt memset 
#define szf sizeof
#define INF 0x3f3f3f3f
#define in(x) scanf("%d", &x)
#define out(x) printf("%d", x)
#define inll(x) scanf("%lld", &x)
#define outll(x) printf("%lld", x)
#define pn printf("\n")
#define con continue
#define bk break
#define vc vector 
#define pb push_back
#define sz size
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 25010, M = 150010;

int n, mr, mp, s; // mr为道路数，mp为航线数
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int id[N]; // id[i]存放点i属于连通块的编号
int bcnt; // 连通块的个数
int bin[N]; // bin[i]表示联通块i的入度
vector<int> b[N]; // b[i]存放连通块i中的点
queue<int> q; // 存放入度为0的连通块
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int bid) { // u为点的编号，bid为连通块的编号
    id[u] = bid, b[bid].pb(u);
    
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!id[j])
            dfs(j, bid);
    }
}

void dijkstra(int bid) {
    priority_queue<PII, vc<PII>, greater<PII>> heap;
    
    for (auto u : b[bid]) heap.push({dist[u], u});
    
    while (heap.sz()) {
        PII t = heap.top();
        heap.pop();
        
        int ver = t.y;
        if (st[ver]) con;
        
        st[ver] = true;
        
        for (int i = h[ver]; ~i; i = ne[i]) {
            int j = e[i];
            
            if (id[ver] != id[j] && -- bin[id[j]] == 0) q.push(id[j]);
            
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                if (id[ver] == id[j]) heap.push({dist[j], j});
            }
        }
    }
}

void topsort() {
    mt(dist, 0x3f, szf dist);
    dist[s] = 0;
    
    flr (i, 1, bcnt)
        if (!bin[i]) q.push(i);
        
    while (q.sz()) {
        int t = q.front();
        q.pop();
        dijkstra(t);
    }
}

int main() {
	in(n), in(mr), in(mp), in(s);
	
	mt(h, -1, szf h);
	while (mr -- ) {
	    int a, b, c;
	    in(a), in(b), in(c);
	    add(a, b, c), add(b, a, c);
	}
	
	flr (i, 1, n) // 处理每个点所在的连通块
	    if (!id[i]) {
	        bcnt ++ ;
	        dfs(i, bcnt);
	    }
	    
	while (mp -- ) {
	    int a, b, c;
	    in(a), in(b), in(c);
	    add(a, b, c), bin[id[b]] ++ ; // 处理每个联通块的入度
	}
	
	topsort(); // 按照拓扑排序来计算最短路
	
	flr (i, 1, n) // 将起点到每个点的最短路输出
	    if (dist[i] > INF / 2) puts("NO PATH"); // 因为有负权边
	    else out(dist[i]), pn;
	
	return 0; // 结束快乐~
}